package Lee_code;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author blh
 * @date 2024年07月30日 8:48
 */
public class Lee_120_730 {
    public int minimumTotal(List<List<Integer>> triangle) {
        List<List<Integer>> dp = new ArrayList<>();
        int n = triangle.size();
        // 放入第一行元素
        dp.add(triangle.get(0));

        for (int i = 1; i < n; i++) {
            List<Integer> oriList = triangle.get(i);
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                // 该行第一个数
                if (j == 0) {
                    temp.add(oriList.get(j) + dp.get(i - 1).get(j));
                }
                // 该行最后一个数
                else if (j == i) {
                    temp.add(oriList.get(j) + dp.get(i - 1).get(j));
                }
                // 中间数
                else {
                    int min = Math.min(dp.get(i - 1).get(j - 1), dp.get(i - 1).get(j));
                    temp.add(oriList.get(j) + min);
                }
            }
            dp.add(temp);
        }
        return dp.get(n-1).stream().mapToInt(Integer::intValue).max().getAsInt();
    }
}
